class Damenproblem {
	private int n;
	int[][] feld;
	
	public Damenproblem (int d) {
		this.n = d;
		feld = new int[d][d];	
	}
	
	public void ausgabe() {
		for (int i=0; i<n; i++){
			for (int j=0; j<n; j++){
				if (j==n-1) System.out.println(feld[i][j]);
				else System.out.print(feld[i][j]+" ");
			}
		}
	}
	
	public boolean korrektPlatziert() {
		for (int zeile = 0; zeile < n; zeile++) {
			for (int spalte = 0; spalte < n; spalte++) {
				if (feld[zeile][spalte]==1) {
					// Zeile überprüfen, es reicht ab der aktuellen Position nach rechts zu suchen
					for (int k = spalte + 1; k < n; k++) {
						if (feld[zeile][k]==1) return false;
					}
					
					// Spalte überprüfen, es reicht ab der aktuellen Position nach unten zu suchen
					for (int k = zeile + 1; k < n; k++) {
						if (feld[k][spalte]==1) return false;
					}
					
					// Diagonalen überprüfen
					for (int k = 1; ((zeile + k) < n) && ((spalte + k) < n); k++) {
						if (feld[zeile + k][spalte + k]==1) return false;
					}										
					for (int k = 1; ((zeile + k) < n) && ((spalte - k) >= 0); k++) {
						if (feld[zeile + k][spalte - k]==1) return false;
					}										
				}				
			}			
		}		
		return true;
	}
	
	public void platziere(int zeile) {
		// die Dame nach und nach in jede Spalte der aktuellen Zeile setzen
		for (int spalte = 0; spalte < n; spalte++) {
			feld[zeile][spalte] = 1; // Dame setzen

			if (korrektPlatziert()) {
				if (zeile >= (n-1)) { // alle Damen gesetzt?
					ausgabe();
					System.out.println ("---------------------------------");
				} else {
					platziere(zeile + 1); // rekursiv die Dame in der nächsten Zeile setzen
				}
			}

			feld[zeile][spalte] = 0; // Dame von der aktuellen Position wieder entfernen
		}
	}
	
}

public class Aufgabe4 {

	public static void main(String[] args) {
		Damenproblem dOk = new Damenproblem (4);
		dOk.feld[1][0] = 1;
		dOk.feld[3][1] = 1;
		dOk.feld[0][2] = 1;
		dOk.feld[2][3] = 1;
		if (dOk.korrektPlatziert()) {
			System.out.println ("dOk ist eine moegliche Loesung!:");
		}
		else {
			System.out.println ("dOk ist keine erlaubte Loesung:");
		}
		dOk.ausgabe();
		
		System.out.println ("---------------------------------");
		
		dOk = new Damenproblem (6);
		dOk.platziere(0);
	}

}
